package cn.bellychang.leetcode.question102;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author ChangLiang
 * @date 2021/2/7
 */
public class Solution2 {

    List<List<Integer>> list = new ArrayList<>();


    public List<List<Integer>> levelOrder(TreeNode root) {

        if (root == null) {
            return list;
        }

        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);

        int currentSize = queue.size();
        // loop invariant: deque空了 说明遍历结束了
        while (currentSize != 0) {
            int nextSize = 0;

            List<Integer> levelList = new ArrayList<>();
            int tempSize = 0;
            while (currentSize!=tempSize) {
                TreeNode poll = queue.poll();
                levelList.add(poll.val);
                tempSize++;

                if (poll.left != null) {
                    queue.offer(poll.left);
                    nextSize++;
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                    nextSize++;
                }
            }
            list.add(levelList);
            currentSize = nextSize;
        }
        return list;
    }
}
